/**
 * Let M(n, d) be the maximum number of repeated digits for an n-digit
 * prime where d is the repeated digit. Let N(n, d) be the number of 
 * such primes. Let S(n, d) be the sum of these primes.
 *
 * For example, M(4, 1) = 3 is the maximum number of repeated digits 
 * for a 4-digit prime where one is the repeated digit, there are 
 * N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275.
 * It turns out that for d = 0, it is only possible to have M(4, 0) = 2 
 * repeated digits, but there are N(4, 0) = 13 such cases.
 *
 * For d = 0 to 9, the sum of all S(4, d) is 273700.
 *
 * Find the sum of all S(10, d).
 */

#include <iostream>
#include <vector>
#include "euler/combination.hpp"
#include "euler/tuple.hpp"
#include "euler/digits.hpp"
#include "euler/prime_test.hpp"
#include "euler.h"

BEGIN_PROBLEM(111, solve_problem_111)
	PROBLEM_TITLE("10-digit primes containing the maximum number of repeated digits")
	PROBLEM_ANSWER("612407567715")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("")
	PROBLEM_SPACE_COMPLEXITY("")
	PROBLEM_KEYWORDS("prime")
END_PROBLEM()

static long long S(int n, int d)
{
	// Build a list of the possible digits in each free place.
	// - d cannot appear in any free place;
	// - the first digit cannot be zero;
	// - the last digit cannot be even.
	std::vector<std::vector<int>> allowed(n);
	for (int i = 0; i < n; i++)
	{
		for (int k = 0; k <= 9; k++)
		{
			if (k == d)
				continue;
			if (i == 0 && k == 0)
				continue;
			if (i == n - 1 && k % 2 == 0)
				continue;
			allowed[i].push_back(k);
		}
	}

	// Create a buffer of digits.
	std::vector<int> digits(n);

	// Let f be the number of free digits.
	for (int f = 0; f < n; f++)
	{
		// Let s be the sum of primes.
		long long s = 0;

		// Iterate each possible choice of f free places out of n places.
		euler::combination_generator<int> free(n, f);
		do
		{
			// The first digit must be free if the digit is zero.
			if (d == 0 && (f == 0 || free[0] != 0))
				continue;

			// Set all digits to d.
			std::fill(digits.begin(), digits.end(), d);

			// Generate each possible digit tuple in the free places.
			euler::tuple_lexico_generator<> tgen(f);
			for (int i = 0; i < f; i++)
				tgen.max(i) = (int)allowed[free[i]].size();

			do 
			{
				// Construct the number.
				for (int i = 0; i < f; ++i)
				{
					digits[free[i]] = allowed[free[i]][tgen[i]];
				}

				// Test whether the number is prime.
				long long v = euler::from_digits<10,long long>(
					digits.begin(), digits.end());				
				if (euler::is_prime(v))
				{
					//std::cout << "Prime: " << v << std::endl;
					s += v;
				}

			} while (tgen.next());

		} while (free.next());

		// Return if at least one such prime is found.
		if (s > 0)
			return s;
	}

	// Not found.
	return 0;
}

static void solve_problem_111()
{
#if 0
	const int Digits = 4;
#else
	const int Digits = 10;
#endif

	long long sum = 0;
	for (int d = 0; d <= 9; d++)
	{
		sum += S(Digits, d);
	}
	std::cout << sum << std::endl;
}
